perm filename MEM[OLD,BGB] blob
sn#099404 filedate 1974-04-26 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00027 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00004 00002 4.0 MEMORY - DATA STRUCTURES.
C00006 00003 4.1 The Winged Edge Polyhedron Representation.
C00013 00004 6.2 Three image formats: Video, CRE and FEV.
C00017 00005 KINDS OF CRE NODES.
C00022 00006 CRE LINK AND DATUM NAMES.
C00025 00007 CRE RINGS, TREES, LISTS AND ARRAYS.
C00028 00008
C00033 00009 4.3 Representation of a Geometric Mental Universe.
C00036 00010 MEMORY - TOP LEVEL GEM STRUCTURE.
C00039 00011 4.5 GEOMED Node Formats.
C00043 00012 2 U Universe
C00045 00013 4 C Camera
C00047 00014 6 D Window
C00049 00015 14 B Body
C00051 00016 16 E Edge
C00054 00017 4.6 CRE NODE FORMATS.
C00058 00018 CRE Node Rellocation Bits.
C00060 00019 1. VECTOR & 2. ARC NODE FORMAT.
C00065 00020 3. POLYGON NODE FORMAT.
C00069 00021 4. SHAPE NODE FORMAT.
C00074 00022 5. LEVEL NODE FORMAT.
C00077 00023 6. IMAGE NODE FORMAT.
C00081 00024 7. FILM NODE FORMAT.
C00084 00025 8. EMPTY NODE FORMAT.
C00087 00026 DATA STRUCTURE: IMAGE ARRAYS.
C00091 00027 4.7 Critique.
C00092 ENDMK
C⊗;
4.0 MEMORY - DATA STRUCTURES.
4.0 Introduction.
4.1 The Winged Edge Polyhedron Representation.
4.2 Three Image Representations: Video, FEV and CRE.
4.3 Representation of a 3-D Mental Universe.
4.4 Other Geometric Entities.
4.5 GEOMED Node Formats.
4.6 CRE Node Formats.
4.7 Critique.
4.0 Introduction.
In order to get a computer to deal with the physical world it
must have a data representation on which computations involving
space, time, shape, size and the appearance of things can be done. In
this chapter, a particular representation for physical objects,
images and associated entities is explained. The data structures has
been implemented as small blocks of words containing pointers and
data in the fashion usual to graphics and simulation; an introduction
to this technology can be found in Knuth. Although the latest
language of implementation is PDP-10 machine code, earlier versions
were coded in LISP and SAIL with LEAP.
4.1 The Winged Edge Polyhedron Representation.
A polyhedron in made up of four kinds of nodes: bodies,
faces, edges and vertices. The body node is the head of three rings:
a ring of faces, a ring of edges and a ring of vertices. Each face
and each vertex points at one of the edges on its perimeter. Each
edge points at its two faces and its two vertices. Completing the
structure, each edge node contains a link to each of its four
immediate neighboring edges clockwise and counter clockwise around
face (vertex) perimeters. These last four pointers are the wings of
the edge, which provide the basis for efficient face and vertex
perimeter accessing. Finally,the links of the edge nodes can be
ordered in a consistent fashion over the surface of any polyhedron so
that the surface always has two sides: the inside and the outside.
Klein bottles and worse are precluded by the data structure.
Observe that there are twenty-two link fields in the basic
representation: bodies contain six links, faces three, vertices three
and edges ten. Thus the least number of different link field names we
need to coin is ten; if we warn the reader in advance that a link
name such as PED has different roles depending on whether it applies
to a body, face, edge or vertex.
---------------------------------------------------------------------
TABLE Data Structure Link Names
1. Face Ring of a Body. NFACE PACE
2. Edge Ring of a Body. NED PED
3. Vertex Ring of a Body. NVT PVT
4. First Edge of a Vertex. PED
5. First Edge of a Face. PED
6. The two faces of an edge: NFACE PFACE
7. The two vertices of an edge: NVT PVT
8. The four wing edges of an edge: NCW PCW
NCCW PCCW
---------------------------------------------------------------------
FIGURE - THE WINGED EDGE.
(As viewed from the exterior of a solid).
\ /
NCCW(E) \ / PCW(E)
\ /
\ /
\ /
⊗ PVT(E)
|
|
NFACE(E) E PFACE(E)
|
|
NVT(E) ⊗
/ \
/ \
/ \
NCW(E) / \ PCCW(E)
/ \
A face, edge or vertex can only belong to one body and so
there is only one body node in a given face, edge or vertex ring; and
that body node serves as the head of the ring. The reason for double
pointer rings is for the sake of rapid deletion, which allows local
alterations to a polyhedron's topology without any list searching.
As figure 2.2 suggests, four of these eight pointers are
stored in the same positions and referred to by the same names as the
face and vertex ring pointers; namely the NFACE, PFACE, NVT and PVT
pointers.
There are four ways in which a pair of faces and a pair of
vertices can be placed into the two face positions and two vertex
positions of an edge. By constraining these choices edges can
independently indicate both a linear direction and a surface
orientation.
The single winged edge pointer found in faces and vertices is
kept in the position named PED and it points to one of the edges
belonging to that face or vertex. Although the vertices in figure 2.2
are shown with three edges, vertices may have any number of edges;
those other potential edges would not be directly connected to E and
so were not shown.
6.2 Three image formats: Video, CRE and FEV.
DATA STRUCTURE: BASICS.
The two generic data structures of CRE are arrays and nodes;
there are five kinds of arrays and eight kinds of nodes.
The node
structures is implemented as seven word fixed sized
blocks. The data structure in CRE represents a sequence in
time of video intensity contour maps. Such contour maps are like
topographical elevation contour maps, in that no two contour lines
should ever cross and in that all the contour lines should close.
Consequently, the loops of contours enclose regions; and these
regions overlap in a nested fashion forming a tree like data
structure.
As the general examples of contoured images on page 5
illustrate, a notion that is emphatically not in CRE, is that of a
schematic line drawing. Although the CRE output can be viewed as a
collection of lines on a display screen, people expecting a line
drawing rendition of the given television picture will be
disappointed. A CRE picture is a simple transformation of the
photometry, geometry and topology of the original video image;
whereas the typical line drawing from a human illustrator is a
representation of the scene without photometric information. On the
other hand, the work of an artist such as Peter Max; or a
paint-by-the-numbers grid does resembly CRE output. This is not an
idle coincidance but rather a consequence of whether or not the
artist is trying to represent photometric data by quantum lines.
The explanation of CRE node structures will be presented in
three parts: first, the several kinds of nodes will be briefly
explained; second, the sub structures such as rings, trees and
lists will be discribed; and third, the node formats and their
contents will be explained in detail.
KINDS OF CRE NODES.
The are eight kinds of CRE nodes: Vector, Arc, Polygon,
Shape, Image, Level, Film and Empty.
1. At the very top of all the structure is the film node, the film
node is unique and serves as an OBLIST from which all other nodes
may be reached. The film node embodies the idea of a piece of
celluloid film or a length of magnetic video tape. A film is a
sequence of images taken by the same camera of the same scene with
only a small amount of action between images.
2. An image node represents the familiar two dimensional idea of a
photograph or an oil painting or to be exact a digital video image
of 216 rows by 288 columns of numbers ranging from 0 for dark to 63
for bright. The image is formed by a thin lens and is projected on
a flat image plane. The idea of an image is so common that it is
easy to overlook the wonder of sun light scattering off of surfaces,
refracting thru a lens, and forming a complex pattern called a real
image.
3. Below the image node are the intensity contour levels. A contour
level is a binary image that results from thresholding a gray scaled
image. So an image is composed of levels, and in turn, a level is
composed of polygons.
4. A Polygon node represents the idea of a contour loop which
always closes upon itself and does not cross itself or any other
contour. Contour loops are approximated by a ring of vectors; hence,
the term "polygon". The contour polygons always have at least three
sides and are simply connected.
5. Shape nodes contain data about one or two polygons. The data in a
shape node is not a positive representation of the notion of shape;
but is rather the parameters of allignment and normalization that
must be compensated before shapes can be compared.
6. Vector nodes contain the locus of an image vertex; however since
vectors always belong to a polygon and always have two neighbors;
their counterclockwise neighbor is considered to determine their
vector direction.
7. Arc nodes are vectors that are made by the polygon smoothing
routine; one arc typically replace several vectors. When both arcs
and vectors are being discussed; vectors are strictly horizontal and
vertical, whereas arcs may point in any direction.
8. Empty nodes are an artifact of the fixed node size dynamic
storage allocation mechanism used in CRE. Entities are made by
taking empty nodes from an AVAIL list and entities are killed by
returning their node to the AVAIL list; there is no garbage
collector, but there is a space compactor.
CRE LINK AND DATUM NAMES.
Nodes contain either numerical data or pointers to other
nodes; such node pointers are actual machine addresses and are
called links. The positions within a node where a link is stored are
named and are reserved for particular uses. In the table below the
11 link names and 13 datum names are introduced. The link names
will always appear capitalized.
11 LINK NAMES:
CW clockwise
CCW counter clockwise
DAD parent of node up a tree structure.
SON descendent of a node down a tree structure.
ENDO Greek for inside, polygon within.
EXO Greek for outside, surrounding polygon.
ALT alternate.
NGON negative polygon.
PGON positive polygon.
NTIME negative in real time, into the past.
PTIME positive in real time, into the future.
13 DATUM NAMES:
Boolean datums.
type type of node bits.
reloc rellocation of node bits.
Fixed point datums.
row row of image locus.
col column of image locus.
cntrst contrast of an edge, vector and arc.
ncnt number count, various uses.
Floating point datums.
zdepth z depth from camera lens center.
perm length of perimeter.
area area in pixel units.
mxx moment of inertia about X axis.
myy moment of inertia about Y axis.
mzz moment of inertia about Z axis.
pxy product of inertia with respect
to the X and Y axes.
CRE RINGS, TREES, LISTS AND ARRAYS.
CRE inputs an image into an array called TVBUF; it makes the
node structures, some of which are temporary; and it outputs a final
version of the structure representing a film of images. The
temporary structures are relevant to understanding the process; but
only the final structure is relevant to using CRE output. In
summary, the important structures are:
FOUR RINGS.
1. Image ring of the film.
2. Level ring of an image.
3. Polygon ring of a level.
4. Vector ring of a polygon.
TWO TREES.
1. The tree of rings.
2. The tree of nested polygons.
TWO LISTS.
1. Time line lists.
2. The empty node list.
TEMPORARY STRUCTURES.
1. Arc rings of polygons.
2. Fusion shape rings of levels.
FIVE ARRAYS.
1. TVBUF - 216 rows, 288 columns of 6 bit bytes.
2. PAC - 216 rows, 288 columns of 1 bit bytes.
3. VSEG - 216 rows, 289 columns of 1 bit bytes.
4. HSEG - 217 rows, 288 columns of 1 bit bytes.
5. SKY - 216 rows, 289 columns of 18 bit bytes.
There is one film node. The film is composed of a ring of
images. Each image is composed of a ring of levels. Each level is
composed of a ring of polygons. Each polygon is composed of a ring
of vectors. The ring structures are implemented with the four links
named DAD, SON, CW and CCW. The rings are headless only in the
sense that all the elements of a ring are brothers; a pointer to the
head of a ring is stored in the DAD link of each element. The DAD of
the film node is NIL; and NIL is an 18-bit zero. The final SON of
all vector nodes is also NIL. The DAD and SON links form a tree of
rings.
Besides the tree of rings, there is the tree of nested
polygons. The nested polygon tree is implemented with the four
links named ENDO, EXO, NGON and PGON. The EXO of a polygon points
at its surronding polygon. The ENDO of a polygon points at one of
the polygons that may be enclaved within the given polygon; and the
NGON and PGON links form a ring of polygons that have the same EXO
polygon.
The time line lists run thru arc and polygon nodes. In the
simple case, the time line links of a polygon point to a
corresponding polygon in the image previous (NTIME) or subsequent
(PTIME) of the current polygon. The correspondence being that the
time polygon is exactly the same intensity at nearly the same
location, orientation, and size as the given polygon. In the case of
polygon fusion, the time line link of a polygon points to a time
polygon of which the given polygon becomes a part. In the case of
polygon fission, the time line link of a polygon points to only one
the pieces into which the given polygon splits.
The time line links of an arc vector point to a
corresponding arc vector in the image previous or subsequent of the
current arc vector. The polygons of arc vectors mated in time are
also mated in time; because after polygon time line links have been
made, one polygon is temporarily translated, rotated and dilated so
as to have the same lamina inertia tensor as its mate; that is the
locus of the arc vectors of one polygon are temporarily altered;
then the corresponding arc vectors are found and their time line
linkages are made.
The empty node list is maintained in the CCW link positions;
the last empty node contains a zero link. All nodes are explicitly
made from and killed to the empty node list by the subroutines
MKNODE and KLNODE.
The arc ring of a polygon is just like a vector ring except
that the pointer to it is stored in the ALT link of the polygon,
while the polygon has both a ring of vectors and a ring of arcs.
The fusion shape ring of a intensity level runs thru the CW
and CCW links of shape nodes and is pointed at by the ALT link of
the level. Fusion shape nodes are the shapes generated to represent
pairs of polygons unmated in time.
4.3 Representation of a Geometric Mental Universe.
At the top of the data structure is a single universe node
from which everything else can be reached. Immediately below the
universe node is a ring of world models. A robot dealing with
physical world sensor input, such as video data, has one of its world
models dedicated to simulating the immediate here and now; this
mental world is called the reality world model. In addition to the
reality world, a robot may have fantasy world models for problem
solving, planning or for recalling platonic object prototypes. In the
following, a two world mental universe will be the most common, with
the reality world being referred to as a "map" and the fantasy world
being referred to as a "dictionary".
Geometric world models have four basic kinds of nodes:
body, face, edge and vertex. The face, edge and vertex nodes are used
to form polyhedrons which may be attached to body nodes. Body nodes
in turn are connected to each other in rings and trees to form a
world model. Additional kinds of nodes discribe cameras and light
sources as well as temporary data such as shadows, spines, and
trajectories.
The image data structure presented in this section is a
computer's internal notation for what is vulgarly called a line
drawing; the common term is misleading because it does not suggest
the equally important space between the lines; terms closer to the
idea would be "mosaic drawing" or "stained glass window drawing".
The data structure has main levels: TV raster, video
intensity contour, arc contour, and region-edge.
MEMORY - TOP LEVEL GEM STRUCTURE.
The top level of the GEM data structure is constructed out
of six kinds of nodes: UNIVERSE, WORLD, IMAGE, WINDOW, CAMERA and
LAMP; by way of contrast the polyhedron data structure consists of
BODY, FACE, EDGE, and VERTEX nodes; and the auxillary nodes are
classified as EMPTY, FRAME, XNODE, YNODE and ZNODE. Initially there
is no image node and only one Universe, World, Window, Camera and
Lamp Node. The approximate interconnections of the nodes is:
←← UNIVERSE →→
/ ↓ \
/ empty nodes \
worlds displays
↓ ↓
↓ windows
↓ ↓
lamps ←←←← WORLD →→→→ cameras ←←←← WINDOW
↓ ↓ ↓
LAMP ↓ CAMERA
↓ / \
↓ synthetic perceived
↓ images images
↓ ↓ ↓
↓ ↓ ↓
↓ ↓ ↓
3-D bodies 2-D bodies
↓ ↓
faces, edges and vertices.
Now for the casual definitions of the SIX top nodes. The
Universe node is unique and all nodes are connected to it so that it
serves as an OBLIST node. The GEM universe is the mental universe or
universe of discourse for geometric modeling. Immediately below the
universe node is a ring of world nodes and a ring or displays (and a
list of empty nodes). A world node is for representing one physics
like world at a particular moment in time; three kinds of worlds
might include a perceived here-and-now world or map; a desired or
goal world; and a world of prototype platonic forms, or dictionary
world. The world points immediately at a ring of light sources
(lamps), a ring of physical camera models, and a ring of bodies.
4.5 GEOMED Node Formats.
0 R Frame
----------------------------
-3 | xwc | X
-2 | ywc | Y World coordinates
-1 | zwc | Z
0 | ix | X
1 | iy | Y i Unit vector
2 | iz | Z
3 | jx | X
4 | jy | Y j Unit vector
5 | jz | Z
6 | kx | X
7 | ky | Y k Unit vector
8 | kz | Z
----------------------------
The frame node contains the location and orientation of an
entity with repect to world coordinates. The locus coordinates are in
centimeters. The world origin and orientation, of course, are defined
outside of GEOMED - for the cart project the world origin is at the
center of the laboratory building's circular arc 440 feet above sea
level, the Z axis is striaght up... For the hand/eye project the
origin is at the corner of the table nearest the golden arm, the Z
axis points up the X axis points towards the blue Sierra camera, the
Y axis points towards the blue arm.
---------------------------------------------------------------------
1 M Empty
The list of empty nodes is maintained in the +1 cdr link.
The last empty node contains a zero address pointer. All the word
of the empty node besides -3 and 0 contain zero.
---------------------------------------------------------------------
2 U Universe
----------------------------
-3 | Coresize |
-2 | |
-1 | Block Count |
0 | type 2 |
1 | Avail |
2 | | Contains base of free storage for I/O
3 | |
4 | son | World Ring
5 | |
6 | |
7 | |
8 | |
----------------------------
The universe node is unique; it is the first node in a GEOMED
address space. Immediately accessible from the universe node is the ring
of world, the empty node list, and the ring of displays.
---------------------------------------------------------------------
3 S SUN
----------------------------
-3 | |
-2 | |
-1 | |
0 | type 3 |
1 | |
2 | |
3 | |
4 | pwrld |
5 | bro (sun ring) sis |
6 | alt frame |
7 | 0 |
8 | |
----------------------------
The sun node represents a light source, however it is very much
like a camera.
---------------------------------------------------------------------
4 C Camera
----------------------------
-3 | scalex |
-2 | scaley |
-1 | scalez |
0 | type 4 |
1 | pdx ldx |
2 | pdy ldy | Physical and logical raster size
3 | focal ldz |
4 | DAD SON | DAD(camera)=universe
5 | BRO SIS | World ring
6 | FRAME | Camera frame of reference
7 | |
8 | |
----------------------------
---------------------------------------------------------------------
5 W World
----------------------------
-3 | |
-2 | pname1 |
-1 | pname2 |
0 | type 5 |
1 | PFACE | Potentially visible face list
2 | NED PED | Ends of potentionally visible edge list
3 | | After SHOW, PED is head of visible edge list
4 | DAD SON | DAD(world)=universe
5 | BRO SIS | World ring
6 | FRAME | World frame
7 | CW CCW | Body ring (all bodies in this world)
8 | |
----------------------------
6 D Window
----------------------------
-3 | sx sy | Source origin
-2 | ox oy | Object origin
-1 | mag | Magnification
0 | type 6 |
1 | XL XH | 2D Clipper window
2 | YL YH |
3 | |
4 | DAD SON | DAD(window)=universe
5 | BRO SIS | World ring
6 | ALT ALT2 | ALT(window)=camera, ALT2(window)=world or image
7 | |
8 | |
----------------------------
7 I Image
----------------------------
-3 | |
-2 | |
-1 | |
0 | type 7 |
1 | NFACE PFACE | Face ring
2 | NED PED | Edge ring
3 | NVT PVT | Vertex ring
4 | DAD SON | DAD(image)=universe
5 | BRO DAD | World ring
6 | |
7 | |
8 | |
----------------------------
14 B Body
----------------------------
-3 | |
-2 | pname1 |
-1 | pname2 |
0 | type 14 |
1 | NFACE PFACE | Face ring
2 | NED PED | Edge ring
3 | NVT PVT | Vertex ring
4 | DAD SON | Parts tree
5 | BRO SIS | Parts tree
6 | ALT FRAME | ALT temporary, FRAME is body frame of reference
7 | CW CCW | Body ring
8 | CAR8 CDR8 | Reserved for users
----------------------------
15 F Face
----------------------------
-3 | AA | Face coefficients (Perspective coordinates)
-2 | BB |
-1 | CC | AA x + BB Y + CC Z = KK
0 | type 15 |
1 | NFACE PFACE | Face ring
2 | (NCNT) PED | PED: First Edge
3 | KK | [Face coefficient]
4 | (DAD) (SON) | (Nested polygon tree)
5 | (BRO) (SIS) |
6 | ALT POTEN | ALT temporary,,Potentially visible face list
7 | QQ | Photometric characteristics (4 9-bit bytes, CRBG)
8 | CAR8 CDR8 | Reserved for users
----------------------------
16 E Edge
----------------------------
-3 | x1dc AA y1dc | 2D Clipper: Edge display coordinates
-2 | x2dc BB x2dc | OCCULT: 2D Edge coefficients AA Xpp + BB Ypp + CC = 0
-1 | naf CC paf | Body Intersection: Temperaries
0 | type 16 |
1 | NFACE PFACE | Two Faces of the edge
2 | NED PED | Edge ring
3 | NVT PVT | Two vertices of the edge
4 | NCW PCW | Wings: Negative and positive clockwise
5 | NCCW PCCW | Wings: Negative and postive counter-clockwise
6 | ALT ALT2 | Temperaries, ALT2 is visible edge list
7 | UFACE PBODY | [OCCULT, BIN] Under[Over]face
8 | CAR8 CDR8 | Reserved for users
----------------------------
17 V Vertex
----------------------------
-3 | Xwc | X
-2 | Ywc | Y World coordinates
-1 | Zwc | Z
0 | type 17 |
1 | xdc ydc | Display coordinates (currently REAL)
2 | TJOINT/PY PED | OCCULT: TJOINT, GEOMED: PY,,First edge
3 | NVT PVT | Vertex ring
4 | Xpp | X
5 | Ypp | Y Perspective projected
6 | ALT Zpp ALT2 | Z or temperary
7 | CAR7 CDR7 | Temperary
8 | CAR8 CDR8 | Reserved for users
----------------------------
4.6 CRE NODE FORMATS.
DATA STRUCTURE: TYPE BITS.
Each node has a word reserved for a boolean vector of 36
values, or bits. The first eighteen bits are called the type bits
and are individually named as follows:
_____________________________________________________________________
for 0 WESBIT westward vector.
vectors 1 SOUBIT southward vector.
only 2 EASBIT eastward vector.
3 NORBIT northward vector.
_____________________________________________________________________
4 NFUSE NTIME polygon fusion.
5 NFISS NTIME polygon fission.
for 6 NEXCT NTIME polygon exact match.
polygons
only 7 PFUSE PTIME polygon fusion.
8 PFISS PTIME polygon fission.
9 PEXCT PTIME polygon exact match.
_____________________________________________________________________
10 HOLBIT Hole polygon bit.
modify 11 ARCBIT Arc vector bit.
_____________________________________________________________________
12 SBIT Shape node bit.
13 VBIT Vertex node bit.
14 PBIT Polygon node bit.
kind
15 LBIT Level node bit.
16 IBIT Image node bit.
17 FBIT Film node bit.
_____________________________________________________________________
The first four bits WESBIT, SOUBIT, EASBIT and NORBIT apply
only to vectors and indicate the direction of the vector. The next
six bits NFUSE, NFISS, NEXCT, PFUSE, PFISS, PEXCT are set by the
polygon compare routine to indicate the kind of time mating found;
where N and P mean negative time or postive time linkage; fusion
means that the given polygon and another polygon fuse to form the
time polygon, two into one; fission means the given polygon splits,
one into two; and exact means that the given polygon matchs one for
one with its time polygon.
The next two bits HOLBIT and ARCBIT indicate distinguished
polygons and vectors respectively. Only one of the last six bits:
SBIT, VBIT, PBIT, LBIT, IBIT and FBIT may be on in a node. These
bits indicate the node's type.
CRE Node Rellocation Bits.
The next eighteen bits are called the reloc bits and
indicate whether or not a link is stored in a particular position of
the node. The rellocation bits are used to compact the CRE node
space for output.
18 unused
19 CAR(WORD0)
20 CDR(WORD0)
21 unused
22 CAR(WORD1)
23 CDR(WORD1)
24 unused
25 CAR(WORD3)
26 CDR(WORD3)
27 unused
28 CAR(WORD4)
29 CDR(WORD4)
30 unused
31 CAR(WORD5)
32 CDR(WORD5)
33 unused
34 CAR(WORD6)
35 CDR(WORD6)
The CAR of a word is the left half. The CDR of a word is the
right half. In the node diagrams the rellocation of each word is
indicated directly to its right as 0, 1, 2 or 3 meaning no
rellocation, left only, right only, and rellocate both halves,
respectively.
1. VECTOR & 2. ARC NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | vector ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | polygon | arc or vector | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0003 |
_____|___________________|___________________|
word | row | col |
3 | 0000.00 | 0000.00 | 0
_____|___________________|___________________|
word | cntrst | ncnt |
4 | | length | 0
_____|___________________|___________________|
word | |
5 | zdepth | 0
_____|_______________________________________|
word | | |
6 | NTIME time line PTIME | 3
_____|___________________|___________________|
The format of vectors and arcs is identical. Inside CRE the
term "vector" has the connotation of being strictly a horizontal or
vertical generated by the contouring step; whereas an arc is a
vector generated by the smoothing step. Vectors contain the
fundamental geometric datum of an image locus. The image locus is
stored in the halfword datums named row and col, which contain the
row and column of a point in units 1/64 of a pixel. (A "pixel" is a
"picture element"). Vectors and arcs also contain the photometric
datum of edge contrast.
Vectors always belong to a polygon node, a pointer to the
polygon of each vector is stored in the link named DAD; as members
of a polygon the vectors form a loop which is always connected so that
each vertex has a neighboring vertex in the clockwise and in the
counter clockwise directions about the polygon's perimeter; these
perimeter pointers are stored in the link positions named CW and
CCW. Vectors never cross, arcs cross on occassions but can be fixed.
The ncnt datum of arcs and vectors contains their length.
The time line links, NTIME and PTIME, may point to a corresponding
arc or vector in the image previous or subsequent to the current
image. (The zdepth datum contains a positive number indicating
distance from the camera's image plane; the zdepth computation is
not properly implemented as of May 1973).
3. POLYGON NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | polygon ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | level | 1st vector | 3
_____|___________________|___________________|
word | type | reloc |
2 | 10 | 33 3233 |
_____|___________________|___________________|
word | ENDO | EXO |
3 |1st polygon within |polygon surround me| 3
_____|___________________|___________________|
word | ALT | ncnt |
4 | shape {or 1st arc}| number of sides | 2
_____|___________________|___________________|
word | NGON | PGON |
5 | nest bro polygon | nest sis polygon | 3
_____|___________________|___________________|
word | | |
6 | NTIME time line PTIME | 3
_____|___________________|___________________|
Every polygon belongs to a level pointed at by the DAD link;
the ring of polygons of a level is formed in the CW and CCW links;
the son of a polygon is its first vector (or arc after the polygon
has been smoothed) and that first vector has the upper left most
locus of any vector of the polygon.
The ENDO, EXO, NGON, PGON are used to form the nested
polygon tree. Every polygon has non-NIL NGON and PGON links; the
trivial case being that the polygon points at itself twice. Every
polygon except one, the outer border polygon, has a non-NIL EXO
link. Every polygon that surrounds one or more other polygons has a
non-NIL ENDO link.
The ALT link position of a polygon temporarily points to the
first arc of a polygon during smoothing when a polygon has both
vectors and arcs. The final contents of the ALT link is a pointer to
the shape node of the polygon. The ncnt datum indicates the number
of sides of the polygon.
The time line of polygons runs thru the NTIME and PTIME
links which point either to a nearly exact match of a polygon; or to
a fusion polygon of a two for one match; or to one of the two
fission parts of a one for two match; (to find the other fission
part, the time links of the vectors must be scanned).
4. SHAPE NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | fusion shape ring | 3
_____|___________________|___________________|
word | perm | area |
1 | | | 0
_____|___________________|___________________|
word | type | reloc |
2 | 10 | 30 0030 |
_____|___________________|___________________|
word | row | col |
3 | 0000.00 | 0000.00 | 0
_____|___________________|___________________|
word | pxy | mzz |
4 |product of inertia | Z-axis moment | 0
_____|___________________|___________________|
word | NGON | PGON |
5 | fusion polygon | main polygon | 3
_____|___________________|___________________|
word | mxx | myy |
6 | X-axis moment | Y-axis moment | 0
_____|___________________|___________________|
The shape node contains the data necessary for normalizing
two polygons so that only their shapes remain. In particular, the
row and col of a shape node is the center of mass of the polygon;
area is the area; perm is the length of perimeter; and mxx, myy,
mzz, pxy is the polygons inertia tensor (from which the principle
angle of orientation can be computed). When given two shapes, the
centers of mass may be alligned; the principle angles may be allign;
and the areas (or permeter) of the two may be normalized.
There are two kinds of shapes: polygon shapes and fusion
shapes. Polygon shapes correspond to a single polygon pointed at by
the PGON link. The CW, CCW and NGON links of a polygon shape are
NIL. Fusion shapes are temporary nodes belonging to a level as a
ring thru CW and CCW. Fusion shapes correspond to the summation of
two unmated polygons which are pointed to by the NGON and PGON
links. The expressions relating to the inertia tensor and to fusion
summation are given in the section on polygon comparing.
The datums named perm, area, pxy, mxx, myy, mzz contain the
left half of a PDP-10 floating number. (Technical note: half of a
floating number has 9 bits of precision and should be expanded to
full word by using the (mirabile dictu !) HLLE instruction in order
to avoid an illegal floating zero caused by truncating numbers like
-1023.0; in CRE, only the product of inertia will ever be negative).
5. LEVEL NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | level ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | image | 1st polygon | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0200 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | ALT | ncnt |
4 | (1st fusion shape)|threshold cut level| 2
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
Every level belongs to an image pointed to by the DAD link;
the ring of levels of an image is formed in the CW and CCW links;
the son of a level is its first polygon and that first polygon is
the upper left most polygon of the level.
The ncnt datum of a level contains its threshold cut value,
which is an integer between -1 and 63. The -1 level is always
generated, and it contains a single polygon with four sides. The -1
level's polygon is called the border polygon; the fiction being that
every point beyond the edges of the televsion picture has an
intensity value of -2, which is blacker than black.
The ALT link of a level contains a temporary pointer to that
level's ring of fusion shapes during polygon compare time mating.
6. IMAGE NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | image ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | film | 1st level | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
Every image belongs to the film pointed to by the DAD link;
the ring of images of the film is formed in the CW and CCW links;
the son of an image is its first level and that first level is the
-1 intensity cut level of the image.
Although an affront to common sense, the counter clockwise
direction about the image ring is positive or later in time and the
clockwise direction is negative or earlier in time. I achieved this
curio by consistently adhereing to the mathematical convention of
counter clockwise as positive; and a day came when counter clockwise
around a ring of real time events was represented in the same manner
as counter clockwise around a polygonal ring of edges.
All the empty space in the image node is reserved for camera
specification data.
7. FILM NODE FORMAT.
_____________________________________________
word | | CCW |
0 | | 1st empty | 1
_____|___________________|___________________|
word | DAD | SON |
1 | 0 | 1st image | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
The film node is unique; it is the first node in a CRE
output file; the SON of film is its first image; the DAD of a film
is NIL; the CCW of a film is a pointer to the 1st empty node;
however, because the nodes are compacted for output and then
relocated with respect to the film node; the final empty node
pointer indicates the number of words of data in the CRE file.
8. EMPTY NODE FORMAT.
_____________________________________________
word | | CCW |
0 | --- | avail | 1
_____|___________________|___________________|
word | | |
1 | --- | --- | 0
_____|___________________|___________________|
word | type | reloc |
2 | | 00 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
The list of empty nodes is maintained in the CCW link
postion; the last empty node contains a zero or NIL link. At present
all the other words of an empty node are zero.
FIGURE SHOWING RASTER STRUCTURE._____________________________________
↑
↑
NORTH
grid point R,C R,C+1
o____HSEG______o
|
|
|
←←←WEST VSEG PIXEL(R,C) EAST→→→
|
|
|
o SOUTH
R+1,C ↓
↓
_____________________________________________________________________
DATA STRUCTURE: IMAGE ARRAYS.
There are five arrays in CRE: TVBUF, Television Buffer; PAC,
Picture Accumulator; VSEG, vertical segments; HSEG, horizontal
segments; and SKY, background sky blue array. The dimensions are:
FIVE ARRAYS.
1. TVBUF - 216 rows, 288 columns of 6 bit bytes.
2. PAC - 216 rows, 288 columns of 1 bit bytes.
3. VSEG - 216 rows, 289 columns of 1 bit bytes.
4. HSEG - 217 rows, 288 columns of 1 bit bytes.
5. SKY - 216 rows, 289 columns of 18 bit bytes.
Inside CRE, the video image size was fixed at 216 rows of
288 columns of 6 bits per pixel. My original idea was to write a
vision operator that would be applied on a small fixed sized window;
so I have had windows 2 by 2; 2 by 3; 4 by 9; 32 by 36; 72 by 96;
and 216 by 288. That is 216=2*2*2*3*3*3 and 288=2*2*2*2*2*3*3.
Having a fixed window size avoids a morass of word packing, array
allocation and window splicing. Having a window size constructed
out of powers of 2 and 3 simplifies what word packing is required
and allows me to do area and space computations in my head.
The image arrays of CRE are of course two dimensional with
the coordinates in row and columns. Row number increases going down
image, in the negative Y axis direction, which is also called the
direction south. Column numbers increase going right on the image,
in the positive X axis direction, which is also called the direction
east. Video picture elements, or "pixels" are thought of as
expressing the intensity of a square cell; the cells are numbered
from 0 to 215 rows, 0 to 287 columns; the number of a cell is the
grid locus of its upper left (northwest) corner; the center locus of
a cell is at (row+1/5,col+1/2). A pixel cell is surrounded by four
segments; the horizontal segments are numbered 0 to 216 rows, 0 to
287 columns; the number of an HSEG is the grid locus of its left
(west) end point. The vertical segments are numbered 0 to 215 rows,
0 to 288 columns; the number of a VSEG is the grid locus of its
upper (north) end point. These conventions are suggested in the
diagram at the bottom of page 19.
4.7 Critique.
The most glaring flaw in the present data structure is that
there is two of them: a 2-D CRE structure and a 3-D GEOMED structure.
This difficulty arose because the directly addressible memory on
Stanford A.I. computer varies between 100K to 150K words. Although
the PDP-KA10 address space is 256K, there was no "virtual memory" or
paging at Stanford and so the problem had to broken up in someway.